package leetcode.hot100;

import java.util.HashSet;

/**
 * leetcode-hot100: 缺失的第一个正数
 * 测试链接: https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 */
public class FirstMissingPositive {

    /**
     * 方法一：利用哈希表,时间复杂度 O(n),空间复杂度 O(n)
     * @param nums
     * @return
     */
    public int firstMissingPositive1(int[] nums) {
        int n = nums.length;
        int max = Integer.MIN_VALUE;
        HashSet<Integer> hash = new HashSet();
        for(int i = 0; i < n; i++){
            hash.add(nums[i]);
            max = Math.max(max, nums[i]);
        }
        if(max <= 0){
            return 1;
        }
        for(int i = 1; i <= max; i++){
            if(!hash.contains(i)){
                return i;
            }
        }
        return max + 1;
    }

    /**
     * 方法二: 时间复杂度 O(n), 空间复杂度: O(1)
     *
     * 原地哈希（将数组视为哈希表）只使用常数级别的空间
     * 数组长度为n，要找的数字一定在[1, n + 1]区间内
     * 可以把每个数字安排到对应的位置上，将数字i安排在下标i-1位置上（相当于自己写的哈希函数映射）
     * 之后再遍历数组检查，第一个不在位置上的数字就是缺失的最小正数
     * @param nums
     * @return
     */
    public int firstMissingPositive2(int[] nums) {
        int n = nums.length;
        for(int i = 0; i < n; i++){
            //如果当前数字在[1,n]中，但没有处于正确的位置上
            while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]){
                //交换
                swap(nums, nums[i] - 1, i);
            }
        }
        //找出第一个不匹配的数字
        for(int i = 0; i < n; i++){
            if(nums[i] != i + 1){
                return i + 1;
            }
        }
        //所有的数字都在正确的位置上
        return n + 1;
    }

    public static void swap(int[] nums, int index1, int index2){
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }
}
